#if 0

#include "crt.h"
//#include "octree.h"
#include "crtmath.h"
#include "crtutil.h"
#include <algorithm>


#define OCTREE_MAX_TRI_PER_LEAF		(12)

/*
/////////////////////////////////////////////////////////////////////////
	Helper functions
/////////////////////////////////////////////////////////////////////////
*/
 
bool TriangleIntersectAABB(TCRTVertexMini v[3], AABB& aabb)
{
	// calculate the aabb for triangle
	AABB _aabb;

	_aabb.Init();
	_aabb += v[0];
	_aabb += v[1];
	_aabb += v[2];

	if (_aabb.minV.x > aabb.maxV.x 
		|| _aabb.maxV.x < aabb.minV.x 
		|| _aabb.minV.y > aabb.maxV.y 
		|| _aabb.maxV.y < aabb.minV.y 
		|| _aabb.minV.z > aabb.maxV.z 
		|| _aabb.maxV.z < aabb.minV.z)
		return false;
	else
		return true;
}

// return a minimum value v, so that 8^v >= a
int Log8(int a)
{
	int result = 0;
	while (a > 0)
	{
		result ++;
		a >>= 3;
	}

	return result;
}


/*
/////////////////////////////////////////////////////////////////////////
	TOctreeLeaf
/////////////////////////////////////////////////////////////////////////
*/

//void TOctreeLeaf::Init(TOctree* tree, AABB& _aabb, int curdepth)
//{
//	empty	= true;
//	aabb	= _aabb;
//
//	triangles.clear();
//}

void TOctreeLeaf::PushTriangle( int triIndex, TCRTVertexMini /*v*/[3] )
{
	triangles.push_back( triIndex );
	empty = false;
}

void TOctreeLeaf::UpdateTriangleAABB(TOctree* pTree)
{	
	triangleAABB.Init();

	TCRTMesh* mesh = pTree->mesh;
	for (size_t i = 0; i < triangles.size(); i++)
	{
		int nTriangleIndex = triangles[i];
		TCRTTriangle& triangle = mesh->triangles[nTriangleIndex];
		for (int j = 0; j < 3; j++)
		{
			VEC3& vertex = mesh->vertices_m[triangle.index[j]];
			triangleAABB += vertex;
		}
	}

	bIsTriangleAABBSmaller = aabb.Contain(triangleAABB);
}

bool TOctreeLeaf::RayIntersect( TOctree* tree )
{
	TCRTMesh* mesh = tree->mesh;
	vector<TSceneIntersection>* info = tree->RI_info;
	bool hit = false;

	if (!empty)
	{
		// check against all the triangles
		for (size_t i = 0; i < triangles.size(); i++)
		{
			int triIndex = triangles[i];
			TCRTTriangleHelper& triHelper = tree->mesh->triangleHelpers[triIndex];

			// Only test the triangle against the ray if the same testing is not performed yet
			if (triHelper.nextTestedHelper == NULL)
			{
				TCRTTriangle& tri = tree->mesh->triangles[triIndex];
				TSceneIntersection newinfo;

				tree->RI_nraytriangle ++;	// stat
				bool TestResult = RayIntersectTriangle( *tree->RI_ray, 
					triHelper,
					newinfo.u, newinfo.v, newinfo.dist );
				triHelper.nextTestedHelper = tree->RI_testedHelper;
				tree->RI_testedHelper = &triHelper;

				if ( TestResult )
				{
					hit = true;

					if (tree->RI_type == ITT_StopOnHit || tree->RI_type == ITT_NearestHit)
					{
						if (newinfo.dist < (*info)[0].dist)	// there'll always be one info in the array in these two cases
						{
							(*info)[0].meshIndex = mesh->meshID;
							(*info)[0].dist = newinfo.dist;
							(*info)[0].u = newinfo.u;
							(*info)[0].v = newinfo.v;
							(*info)[0].index[0] = tri.index[0];
							(*info)[0].index[1] = tri.index[1];
							(*info)[0].index[2] = tri.index[2];
						}

						if (tree->RI_type == ITT_StopOnHit)
							break;
					}
					else
					{
						newinfo.meshIndex = mesh->meshID;
						newinfo.index[0] = tri.index[0];
						newinfo.index[1] = tri.index[1];
						newinfo.index[2] = tri.index[2];

						info->push_back( newinfo );
					}
				}

			}
		}
	}

	return hit;
}

/*
/////////////////////////////////////////////////////////////////////////
	TOctreeNode
/////////////////////////////////////////////////////////////////////////
*/

void TOctreeNode::Init(TOctree* tree, AABB& _aabb, int curdepth)
{
	empty = true;
	aabb = _aabb;

	if (curdepth == tree->depth - 2)
	{
		// child would be leaf
		for (int i = 0; i < 8; i++)
		{
			AABB childAABB = _aabb.OctSplit(i);
			VEC3 childCenter = childAABB.GetOrigin();
			int size = 1 << (tree->depth - 1);
			VEC3 leafSize = tree->root->aabb.GetSize() * (2.0f / float(size));

			int X = int((childCenter.x - tree->root->aabb.minV.x) / leafSize.x);
			int Y = int((childCenter.y - tree->root->aabb.minV.y) / leafSize.y);
			int Z = int((childCenter.z - tree->root->aabb.minV.z) / leafSize.z);

			int index = ((Z << (2 * tree->depth - 2)) + (Y << (tree->depth - 1)) + X);
			child[i] = tree->_curleaf + index;

			//child[i] = tree->_curleaf ++;
			//child[i]->Init( tree, _aabb.OctSplit(i), curdepth + 1 );
		}
	}
	else
	{
		// child would be node
		for (int i = 0; i < 8; i++)
		{
			child[i] = tree->_curnode ++;
			AABB aabb = _aabb.OctSplit(i);
			child[i]->Init( tree, aabb, curdepth + 1 );
		}
	}
}

void TOctreeNode::PushTriangle( int triIndex, TCRTVertexMini v[3] )
{
	bool in = false;
	for (int i = 0; i < 8; i++)
	{
		if ( TriangleIntersectAABB( v, child[i]->aabb ) )
		{
			child[i]->PushTriangle( triIndex, v );
			in = true;
		}
	}

	empty = false;
}

void TOctreeNode::UpdateTriangleAABB(TOctree* pTree)
{
	triangleAABB.Init();

	for (int c = 0; c < 8; c++)
	{
		TOctreeNodeInterface* pChild = child[c];
		pChild->UpdateTriangleAABB(pTree);

		triangleAABB += pChild->aabb;
	}

	bIsTriangleAABBSmaller = aabb.Contain(triangleAABB);
}

// ray - subnode relationship
struct RaySubNodeRel
{
	int childIndex;
	float distance;
};

bool NearerThan(RaySubNodeRel& n0, RaySubNodeRel& n1)
{
	return n0.distance < n1.distance;
}

bool TOctreeNode::RayIntersect( TOctree* tree )
{
	bool hit = false;
	vector<RaySubNodeRel> subNodes;

	if (!empty)
	{
		// Check the relationship between the ray and 8 subnodes
		for (int i = 0; i < 8; i++)
		{
			TOctreeNodeInterface* c = child[i];
			float Distance = FLT_MAX;
			if (RayIntersectAABB( *tree->RI_ray, c->aabb, Distance, tree ))
			{
				RaySubNodeRel subNode;
				subNode.childIndex = i;
				subNode.distance = Distance;

				subNodes.push_back( subNode );
			}
		}

		// Sorting
		sort(subNodes.begin(), subNodes.end(), NearerThan);

		for (size_t i = 0; i < subNodes.size(); i++)
		{
			RaySubNodeRel& subNode = subNodes[i];
			TOctreeNodeInterface* c = child[subNode.childIndex];

			if (c->RayIntersect( tree ))
			{
				hit = true;
				if (tree->RI_type != ITT_AllHits)
					break;
			}
		}
	}

	return hit;
}

/*
/////////////////////////////////////////////////////////////////////////
	TOctree
/////////////////////////////////////////////////////////////////////////
*/

TOctree::TOctree( TCRTMesh* inmesh )
{
	mesh	= inmesh;
	depth	= 1 + Log8((static_cast<int>(mesh->triangles.size()) + OCTREE_MAX_TRI_PER_LEAF - 1) / OCTREE_MAX_TRI_PER_LEAF);

	if (depth < 2)
		depth = 2;	// At least 2 

	int size = 1 << (depth - 1);
	nleaf	= 1 << (3 * (depth - 1));
	nnode	= (nleaf - 1) / 7;

	_node	= new TOctreeNode[nnode];
	_leaf	= new TOctreeLeaf[nleaf];

	_curleaf = _leaf;
	VEC3 leafSize = mesh->aabb.GetSize() * (2.0f / float(size));
	// The leaves are created in order of Z-Y-Z
	// So that random access is efficient
	for (int z = 0; z < size; z++)
	{
		for (int y = 0; y < size; y++)
		{
			for (int x = 0; x < size; x++)
			{
				_curleaf->empty = true;
				_curleaf->aabb.minV  = mesh->aabb.minV + leafSize * VEC3((float)x, (float)y, (float)z);
				_curleaf->aabb.maxV	 = _curleaf->aabb.minV + leafSize;
				_curleaf->triangles.clear();

				_curleaf++;
			}
		}
	}

	_curnode	= _node;
	_curleaf	= _leaf;

	root	= _curnode++;
	root->Init( this, mesh->aabb, 0 );
 
	//for (vector<TCRTTriangle>::iterator it = mesh->triangles.begin(); it != mesh->triangles.end(); it++)
	for (size_t i = 0; i < mesh->triangles.size(); i++)
	{
		TCRTTriangle& tri = mesh->triangles[i];
		TCRTVertexMini v[3];
		//TCRTTriangle& triangle = mesh->triangles[i];

		v[0] = mesh->vertices_m[tri.index[0]];
		v[1] = mesh->vertices_m[tri.index[1]];
		v[2] = mesh->vertices_m[tri.index[2]];

		root->PushTriangle( i, v );
	}

	root->UpdateTriangleAABB(this);
}

TOctree::~TOctree()
{
	delete []_node;
	delete []_leaf;
}


bool TOctree::RayIntersect(RAY* ray, vector<TSceneIntersection>& info, IntersectTestType type)
{
	RI_ray	= ray;
	RI_info = &info;
	RI_type = type; 
	RI_testedHelper = NULL;
 
	bool hit = false;
	bool hitTree = false;

	vector<int> hitLeafArray;
	hitTree = RayIntersectTree( *ray, root->aabb, depth, hitLeafArray, this );

	if (hitTree)
	{
		for (size_t i = 0; i < hitLeafArray.size(); i++)
		{
			TOctreeLeaf* leaf = _leaf + hitLeafArray[i];

			if (leaf->empty)
			{
				continue;
			}

			float Distance = FLT_MAX;
			if (leaf->bIsTriangleAABBSmaller)
			{
				if (!RayIntersectAABB( *RI_ray, leaf->triangleAABB, Distance, this ))
				{
					continue;
				}
			}

			hit |= leaf->RayIntersect(this);
			if (hit && RI_type != ITT_AllHits)
			{
				break;
			}
		}
	}

	// release the tested helper list
	TCRTTriangleHelper* h = RI_testedHelper;
	while (h)
	{
		TCRTTriangleHelper* next = h->nextTestedHelper;
		h->nextTestedHelper = NULL;
		h = next;
	}

	return hit;
}

#endif